from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        w = len(obstacleGrid[0])
        h = len(obstacleGrid)

        # 初始化  我没想到更好的方法
        dp_list = [[0 for col in range(w)] for row in range(h)]

        # 初始化第一行 和 第一列
        for i in range(len(obstacleGrid[0])):
            if obstacleGrid[0][i] == 1:
                break
            else:
                dp_list[0][i] =1
        for i in range(len(obstacleGrid)):
            if obstacleGrid[i][0] == 1:
                break
            else:
                dp_list[i][0] = 1
        # 填充bp数组
        for i in range(1,h):
            for j in range(1,w):

                dp_list[i][j] = dp_list[i][j-1] + dp_list[i-1][j]
                if obstacleGrid[i][j] == 1:
                    dp_list[i][j] = 0
        print(dp_list)
        if w == 1:
            return dp_list[h-1][0]
        if h ==1:
            return dp_list[0][w-1]
        return dp_list[h-1][w-1]


if __name__ == '__main__':
    obstacleGrid = [[1, 1]]
    solution = Solution()
    val = solution.uniquePathsWithObstacles(obstacleGrid)
    print(val)
